package com.hy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 长度为 K 子数组中的最大和
 *
 * 给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
 * 子数组的长度是 k，且
 * 子数组中的所有元素 各不相同 。
 * 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
 * 子数组 是数组中一段连续非空的元素序列。
 *
 * 示例 1：
 * 输入：nums = [4,4,4], k = 3
 * 输出：0
 * 解释：nums 中长度为 3 的子数组是：
 * - [4,4,4] 不满足全部条件，因为元素 4 出现重复。
 * 因为不存在满足全部条件的子数组，所以返回 0 。
 *
 * 提示：
 * 1 <= k <= nums.length <= 105
 * 1 <= nums[i] <= 105
 *
 * User:Mr.Du
 * Date:2024/3/24
 * Time:21:21
 */
public class MaximumSubarraySum {

    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length, r = k, l = 0;
        long res = 0, sum = 0;
        Map<Integer, Integer> mp = new HashMap<>();
        for(int i = 0;i < k;i++){
            mp.put(nums[i], mp.getOrDefault(nums[i], 0) + 1);
            sum += nums[i];
        }
        while(true){
            if(mp.size() == k){
                res = Math.max(res, sum);
            }
            if(r >= n) break;
            // 有重复 or 刚好等于k，重新计算，从左开始移除
            mp.put(nums[l], mp.get(nums[l]) - 1);
            sum -= nums[l];
            if(mp.get(nums[l]) == 0) mp.remove(nums[l]);
            l++;
            mp.put(nums[r], mp.getOrDefault(nums[r], 0) + 1);
            sum += nums[r++];
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new MaximumSubarraySum().maximumSubarraySum(new int[]{1,5,4,2,9,9,9}, 3));
    }

    public long maximumSubarraySum1(int[] nums, int k) {
        Set<Integer> list = new HashSet<>();
        int l = 0, r = 0, n = nums.length;
        long res = 0, sum = 0;
        while(r < n){
            int c = nums[r++];
            while(list.contains(c)){
                list.remove(nums[l]);
                sum -= nums[l++];
            }
            list.add(c);
            sum += c;
            if(r - l == k ){
                res = Math.max(res, sum);
                list.remove(nums[l]);
                sum -= nums[l++];

            }
        }
        return res;
    }
}
